package org.leetcode.middle.leetcode93;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {

    List<String> res = new ArrayList<>();

    StringBuilder item = new StringBuilder();

    public List<String> restoreIpAddresses(String s) {

        int n = s.length();

        if (n < 4 || n > 12) {
            return null;
        }

        backtracking(s, 0, 0);

        return res;
    }

    /**
     * index 为 已经使用过s的下标
     * pointCount 为 ip中段的数量
     */
    private void backtracking(String s, int index, int partCount) {
        if (partCount == 4 && index == s.length()) {
            res.add(new String(item));
            return;
        }

        //不符合
        if (partCount == 4 || index == s.length()) {
            return;
        }

        for (int i = 1; i <= 3 && i + index < s.length(); i++) {

            String str = s.substring(index, index + i);
            //item没有追加元素之前的长度，用于回溯删除元素时使用
            int itemPreLength = item.length();
            if (isValid(str)) {
                if (partCount > 0) {
                    item.append(".");
                }
                item.append(str);
                partCount++;

                backtracking(s, index + i, partCount);

                item.delete(itemPreLength, item.length());
                partCount--;
            }
        }
    }

    private boolean isValid(String str) {

        if (str.length() > 1 && str.startsWith("0")) {
            return false;
        }

        Integer num = Integer.valueOf(str);

        if (num < 0 || num > 255) {
            return false;
        }

        return true;
    }

}
